#include<bits/stdc++.h>

using namespace std;

typedef struct LNode{   //  链表结点的结构定义
    int data;
    struct LNode *next;
}Lnode, *LinkedList;

bool InitList(LinkedList &L) {
    L = (LNode *)malloc(sizeof(LNode)); //  分配一个头结点
    if (L == NULL)  //  内存不足，分配失败
        return false;
    L->next = NULL;
    return true;
}

// 尾插法建立单链表（不使用尾指针）
bool Insert(LinkedList &L, int e) {
    LNode *p = L;
    LNode *s = (Lnode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = e;
    while (p->next != NULL)
        p = p->next;
    p->next = s;
    s->next = NULL;
    return true;
}

int Search_k(LinkedList L, int k) {
    Lnode *p = L->next, *q = L->next;
    // q先移动到第k个结点
    for (int i = 1; i < k; i++) {
        q = q->next;
        if (q == NULL)
            return 0;
    }
    // p和q同时向前移动，直到q移动到最后一个结点
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
    }
    cout << p->data << endl;
    return 1;
}

int main() {
    // 测试
    int k = 2;
    LinkedList L;
    InitList(L);
    // 建立链表：head -> 1 -> 2 -> 3 -> 4 -> 5
    for (int i = 1; i <= 5; i++)
        Insert(L, i);
    cout << Search_k(L, k) << endl;
    return 0;
}